package com.my.collection.graph.v4;

import com.my.collection.graph.v1.ElementExistException;
import com.my.collection.graph.v1.ElementNotFoundException;

import java.util.*;

/**
 * Created by ZhongGang
 * at 2018/10/23 16:29
 * <p>
 * 无向加权图
 */
public class Graph<V> {
    private Map<V, Set<Edge<V>>> table = new HashMap<>();

    public void addVertex(V v) {
        if (this.table.containsKey(v)) {
            throw new ElementExistException();
        }

        this.table.put(v, new HashSet<>());
    }

    public void addEdge(V from, V to, int weight) {
        if (!this.table.containsKey(from) || !this.table.containsKey(to)) {
            throw new ElementNotFoundException();
        }

        this.table.get(from).add(new Edge<>(from, to, weight));
        this.table.get(to).add(new Edge<>(to, from, weight));
    }

    public List<Edge<V>> prim() {
        List<Edge<V>> minEdges = new ArrayList<>();
        Set<V> visited = new HashSet<>();
        Set<V> vertexes = this.table.keySet();

        //初始化顶点
        for (V vertex : vertexes) {
            visited.add(vertex);
            break;
        }

        while (!visited.containsAll(vertexes)) {
            Edge<V> minEdge = null;
            for (V v : visited) {
                Set<Edge<V>> edges = this.table.get(v);
                for (Edge<V> edge : edges) {
                    if (visited.contains(edge.to)) {
                        continue;
                    }

                    minEdge = minEdge == null ? edge : minEdge;
                    if (edge.weight < minEdge.weight) {
                        minEdge = edge;
                    }
                }
            }

            if (minEdge != null) {
                minEdges.add(minEdge);
                visited.add(minEdge.to);
            }
        }

        return minEdges;
    }

    public List<Edge<V>> kruskal() {
        Graph<V> graph = new Graph<>();
        List<Edge<V>> edges = new ArrayList<>();
        for (Map.Entry<V, Set<Edge<V>>> entry : table.entrySet()) {
            graph.addVertex(entry.getKey());
            edges.addAll(entry.getValue());
        }
        Collections.sort(edges);

        for (Edge<V> edge : edges) {
            if (!graph.isCyclic()) {
                graph.addEdge(edge.from, edge.to, edge.weight);
            }
        }

        return graph.getEdges();
    }

    /**
     * 获取图的所有边
     *
     * @return
     */
    public List<Edge<V>> getEdges() {
        List<Edge<V>> edges = new ArrayList<>();
        for (Map.Entry<V, Set<Edge<V>>> entry : table.entrySet()) {
            edges.addAll(entry.getValue());
        }
        return edges;
    }

    /**
     * 图是否有回路产生
     *
     * @return
     */
    public boolean isCyclic() {
        throw new UnsupportedOperationException();
    }

    /**
     * 图的连通分量的个数
     *
     * @return
     */
    public int connectedCount() {
        Set<V> vertexes = this.table.keySet();
        List<V> visited = new ArrayList<>();
        int count = 0;
        for (V vertex : vertexes) {
            if (visited.contains(vertex)) {
                continue;
            }

            Stack<V> stack = new Stack<>();
            stack.push(vertex);
            while (!stack.isEmpty()) {
                V pop = stack.pop();
                visited.add(pop);

                Set<Edge<V>> edges = this.table.get(pop);
                for (Edge<V> edge : edges) {
                    if (!visited.contains(edge.to)) {
                        stack.push(edge.to);
                    }
                }
            }
            count++;
        }
        return count;
    }

    static class Edge<V> implements Comparable<Edge<V>> {
        V from;
        V to;

        Edge(V from, V to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        int weight;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge<?> edge = (Edge<?>) o;
            return Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return Objects.hash(to);
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }

        @Override
        public int compareTo(Edge<V> o) {
            return Integer.compare(this.weight, o.weight);
        }
    }

}
